﻿// LC1011_黎锦坪.cpp 

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        int left = 0, right = 0;
        for (int weight : weights) {
            left = max(left, weight);
            right += weight;
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            int needDays = 1;
            int currentWeight = 0;
            for (int weight : weights) {
                if (currentWeight + weight > mid) {
                    needDays++;
                    currentWeight = 0;
                }
                currentWeight += weight;
            }
            if (needDays <= days) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};
int main() {
    Solution solution;

    vector<int> weights1 = { 1,2,3,4,5,6,7,8,9,10 };
    int days1 = 5;
    cout << "测试用例1: " << solution.shipWithinDays(weights1, days1) << endl;  // 预期输出: 15

    vector<int> weights2 = { 3,2,2,4,1,4 };
    int days2 = 3;
    cout << "测试用例2: " << solution.shipWithinDays(weights2, days2) << endl;  // 预期输出: 6

    vector<int> weights3 = { 5,4,3,2,1 };
    int days3 = 2;
    cout << "测试用例3: " << solution.shipWithinDays(weights3, days3) << endl;  // 预期输出: 7

    return 0;
}
